class Solution 
{
public:
	int minCut(string s) 
	{
		int n = s.size();
		vector<vector<int>> g(n, vector<int>(n, 1));

		// ================= 动态规划判定回文子串 =================
		for (int i = n - 1; i >= 0; i--)
		{
			for (int j = i + 1; j < n; j++)
			{

				g[i][j] = (s[i] == s[j]) & g[i + 1][j - 1];  // g[i][j] 表示 s[i...j] 是否为回文子串
			}
		}

		vector<int> f(n, INT_MAX);         
		for (int i = 0; i < n; i++)
		{
			if (g[0][i])
			{
				f[i] = 0;
			}
			else
			{
				for (int j = 0; j < i; j++)
				{
					if (g[j + 1][i])
						f[i] = min(f[j] + 1, f[i]);
				}
			}
		}
		return f.back();
	}
};